#include <iostream>
using namespace std;

// 链表节点结构
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 链表类定义
class LinkList {
private:
    Node* head;  // 链表头指针

public:
    // 构造函数
    LinkList() : head(nullptr) {}
    ~LinkList() {
        Node* current = head;
        Node* nextNode;
        while (current != nullptr) {
            nextNode = current->next; // 保存下一个节点
            delete current;            // 删除当前节点
            current = nextNode;        // 移动到下一个节点
        }
    }

    // 插入元素到链表尾部
    void insert(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    // 打印链表
    void printList() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << "->";
            temp = temp->next;
        }
        cout << endl;
    }

    // (1) 删除给定元素的算法。
    void deleteElement(int value) {
        if (!head) return;

        // 删除头结点是目标值的情况
        while (head && head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }

        Node* curr = head;
        while (curr && curr->next) {
            if (curr->next->data == value) {
                Node* temp = curr->next;
                curr->next = curr->next->next;
                delete temp;
            } else {
                curr = curr->next;
            }
        }
    }

    // (2) 对于已排好序的线性表，删除所有重复元素的算法。
    void removeDuplicates() {
        if (!head) return;

        Node* curr = head;
        while (curr && curr->next) {
            if (curr->data == curr->next->data) {
                Node* temp = curr->next;
                curr->next = curr->next->next;
                delete temp;
            } else {
                curr = curr->next;
            }
        }
    }

    // (3) 线性表“逆置”算法。
    void reverseList() {
        Node* prev = nullptr;
        Node* curr = head;
        Node* next = nullptr;

        while (curr) {
            next = curr->next;  // 保存下一个节点
            curr->next = prev;  // 当前节点指向前一个节点
            prev = curr;        // 移动 prev 指针
            curr = next;        // 移动 curr 指针
        }
        head = prev;
    }

    // (4) 线性表循环左移/右移 k 位的算法。
    void leftRotate(int k) {
        if (!head || k <= 0) return;

        // 计算链表长度
        Node* temp = head;
        int length = 1;
        while (temp->next) {
            temp = temp->next;
            length++;
        }

        // k 超过链表长度时取模
        k = k % length;
        if (k == 0) return;

        // 将链表连成环
        temp->next = head;

        // 找到新头结点和新尾结点
        Node* newTail = head;
        for (int i = 0; i < k - 1; i++) {
            newTail = newTail->next;
        }
        head = newTail->next;  // 新的头结点
        newTail->next = nullptr;  // 断开环
    }

    // 链表循环右移 k 位
    void rightRotate(int k) {
        if (!head || k <= 0) return;

        // 计算链表长度
        Node* temp = head;
        int length = 1;
        while (temp->next) {
            temp = temp->next;
            length++;
        }

        // k 超过链表长度时取模
        k = k % length;
        if (k == 0) return;

        // 将链表连成环
        temp->next = head;

        // 找到新头结点和新尾结点
        Node* newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail->next;
        }
        head = newTail->next;  // 新的头结点
        newTail->next = nullptr;  // 断开环
    }

    // (5) 合并两个已排好序的线性表的算法。
    static LinkList mergeSortedLists(LinkList& l1, LinkList& l2) {
        LinkList mergedList;
        Node* p1 = l1.head;
        Node* p2 = l2.head;

        while (p1 && p2) {
            if (p1->data < p2->data) {
                mergedList.insert(p1->data);
                p1 = p1->next;
            } else {
                mergedList.insert(p2->data);
                p2 = p2->next;
            }
        }

        // 处理剩余部分
        while (p1) {
            mergedList.insert(p1->data);
            p1 = p1->next;
        }
        while (p2) {
            mergedList.insert(p2->data);
            p2 = p2->next;
        }

        return mergedList;
    }
};

int main() {
    LinkList list1;
    list1.insert(1);
    list1.insert(2);
    list1.insert(2);
    list1.insert(3);
    list1.insert(4);

    cout << "最开始的链表: ";
    list1.printList();

    // 删除元素 2
    list1.deleteElement(2);
    cout<<"(1)删除2之后: ";
    list1.printList();

    cout<<"(2) 对于已排好序的线性表，删除所有重复元素的算法:"<<endl;
    // 删除重复元素
    list1.insert(5);
    list1.insert(5);
    cout << "   加起来有重复的: ";
    list1.printList();
    list1.removeDuplicates();
    cout << "   删除重复的: ";
    list1.printList();


    cout<<"(3) 线性表“逆置”算法：";
    // 逆置链表
    list1.reverseList();
    list1.printList();

    // 链表左移 2 位
    cout<<"(4) 线性表循环左移 2 位的算法: ";
    list1.leftRotate(2);
    list1.printList();

    // 链表右移 2 位
    cout<<"(4) 线性表循环右移 2 位的算法: ";
    list1.rightRotate(2);
    list1.printList();


    // 合并两个已排序的链表
    cout<<"(5) 合并两个已排好序的线性表的算法："<<endl;
    LinkList list2;
    list2.insert(0);
    list2.insert(2);
    list2.insert(5);

    LinkList list3;
    list3.insert(1);
    list3.insert(3);
    list3.insert(4);
    cout<<"    第一个";
    list2.printList();
    cout<<"    第二个";
    list3.printList();

    LinkList mergedList = LinkList::mergeSortedLists(list2, list3);
    cout << "    合并后: ";
    mergedList.printList();

    return 0;
}
